import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T6三数之和 {
    public static void main(String[] args) {
        int[] nums = new int[]{-1,0,1,2,-1,-4};
        System.out.println(threeSum(nums));
    }
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for(int i=0;i<n-2;) {
            //特判
            if (nums[i] > 0) return ret;

            int l = i+1;
            int r = n-1;
            while (l < r) {
                if(nums[l]+nums[r]+nums[i]>0) {
                    r--;
                } else if (nums[l]+nums[r]+nums[i]<0) {
                    l++;
                } else {
                    ret.add(new ArrayList<>(Arrays.asList(nums[l],nums[r],nums[i])));
                    l++;
                    r--;
                    //去重
                    while(l<r && nums[l] == nums[l-1]) l++;
                    while (l<r && nums[r]==nums[r+1]) r--;
                }
            }
            i++;
            //去重
            while (i<n-2 && nums[i]==nums[i-1]) i++;
        }
        return ret;
    }
}
